@PhDThesis{Chagas:2021:MeOvCl,
author = "Chagas, Guilherme Oliveira",
title = "Methods for overlapping clustering optimization problems",
school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
year = "2021",
address = "S{\~a}o Jos{\'e} dos Campos",
month = "2020-11-30",
keywords = "overlapping clustering, overlap control, community detection,
multiple assignment, hybrid heuristic, branch-and-price,
agrupamento com sobreposi{\c{c}}{\~a}o, controle de
sobreposi{\c{c}}{\~a}o, detec{\c{c}}{\~a}o de comunidades,
multi-designa{\c{c}}{\~a}o, heur{\'{\i}}stica
h{\'{\i}}brida.",
abstract = "Clustering problems arise from several areas of science.
Approaches and algorithms are as varied as the applications. The
goal of clustering is to partition a set of elements into disjoint
subsets, also known as clusters, according to a similarity metrics
values. In many real-world applications, however, vertices can
belong to more than one cluster, i.e., clusters may overlap.
Identifying such overlapping clusters is usually a less studied
problem and a more challenging task than finding non-overlapping
ones. Thus, in this work, overlapping clustering problems from
four different contexts are explored. First, it is introduced the
overlapping cluster editing, a new relaxation of the cluster
editing problem. Three hybrid heuristics were developed to
generate solutions for this problem, which are composed of
coupling metaheuristics and mixed-integer linear programs. The
second work introduces a hybrid heuristic for the overlapping
community detection problem, where the objective is to identify
overlapping clusters from an input network. This is achieved by
solving a mixedinteger linear program using, as input, a
heterogeneous set of clusters generated by two state-of-the-art
overlapping community detection algorithms. In the third work, the
p-median problem with overlap control is introduced. This problem
is a variation of the well-known p-median problem, where the
objective is to select p facilities vertices whereas the sum of
the distances from each client vertex to its nearest facility is
minimized. In the p-median problem with overlap control, the
number of vertices shared between facilities can be managed from a
user-defined parameter. A parallel branch-and-price method was
developed to solve this problem. In the fourth work, a parallel
adaptive large neighborhood search metaheuristic was proposed to
solve some facility location problems with multiple assignments.
Several tests results in all problems show that all proposed
methods can generate good-quality overlapping clustering
solutions. RESUMO: Problemas de agrupamento s{\~a}o encontrados
em v{\'a}rias {\'a}reas da ci{\^e}ncia e abordagens e
algoritmos s{\~a}o t{\~a}o variados quanto as
aplica{\c{c}}{\~o}es. O objetivo em um problema de agrupamento
{\'e} particionar um conjunto de elementos em subconjuntos
disjuntos, tamb{\'e}m conhecidos como clusters. Entretanto, em
muitas aplica{\c{c}}{\~o}es de problemas reais, elementos podem
pertencer a mais de um cluster, isto {\'e}, os clusters podem se
sobrepor. Identificar tais clusters sobrepostos {\'e}, em geral,
um problema menos estudado e mais dif{\'{\i}}cil que o problema
original. Ent{\~a}o, neste trabalho, problemas de agrupamento com
sobreposi{\c{c}}{\~a}o, de quatro contextos diferentes, s{\~a}o
explorados. No primeiro contexto, {\'e} introduzido o problema de
edi{\c{c}}{\~a}o de clusters com sobreposi{\c{c}}{\~a}o, uma
nova relaxa{\c{c}}{\~a}o do problema de edi{\c{c}}{\~a}o de
clusters. Tr{\^e}s heur{\'{\i}}sticas h{\'{\i}}bridas foram
desenvolvidas para gerar solu{\c{c}}oes para o problema proposto,
as quais s{\~a}o combina{\c{c}}{\~o}es de
meta-heur{\'{\i}}sticas e problemas lineares inteiros mistos.
Introduz-se, no segundo trabalho, uma heur{\'{\i}}stica
h{\'{\i}}brida para o problema de detec{\c{c}}{\~a}o de
comunidades com sobreposi{\c{c}}{\~a}o. Essa heur{\'{\i}}stica
h{\'{\i}}brida {\'e} composta de um problema linear inteiro
misto que recebe, como entrada, um conjunto de clusters gerado por
duas heur{\'{\i}}sticas no estado da arte de
detec{\c{c}}{\~a}o de comunidades. No terceiro contexto, o
problema de p-medianas com controle de sobreposi{\c{c}}{\~a}o
{\'e} introduzido. Esse problema {\'e} uma varia{\c{c}}{\~a}o
do problema de p-medianas. No problema de p-medianas, o
n{\'u}mero de v{\'e}rtices compartilhados entre as facilidades
pode ser controlado por um par{\^a}metro de entrada. Um algoritmo
paralelo de branch-and-price foi implementado para resolver esse
problema. No quarto contexto, uma meta-heur{\'{\i}}stica
Adaptive Large Neighborhood Search paralela foi aplicada a
tr{\^e}s problemas de localiza{\c{c}}{\~a}o de facilidades com
multi-designa{\c{c}}{\~a}o. V{\'a}rios testes foram realizados
em todos os quatro contextos e os m{\'e}todos propostos puderam
gerar boas solu{\c{c}}{\~o}es de agrupamento com
sobreposi{\c{c}}{\~a}o.",
committee = "Korting, Thales Sehn (presidente) and Lorena, Luiz Ant{\^o}nio
Nogueira (orientador) and Santos, Rafael Duarte Coelho dos
(orientador) and Queiroz, Gilberto Ribeiro de and Chaves, Antonio
Augusto and Coelho, Leandro Callegari",
englishtitle = "M{\'e}todos para problemas de otimiza{\c{c}}{\~a}o de
agrupamentos com sobreposi{\c{c}}{\~a}o",
language = "en",
pages = "145",
ibi = "8JMKD3MGP3W34R/43MTEC5",
url = "http://urlib.net/ibi/8JMKD3MGP3W34R/43MTEC5",
targetfile = "publicacao.pdf",
urlaccessdate = "01 maio 2024"
}